package mcjunkin;
import java.io.*;
import java.util.*;
import java.security.*;


/**
	This class implements the actual match algorithm.
*/

public class MatchFinder{

	//listeners
	private ProgressListener pl;
	private MatchListener ml;
	private StatusListener sl;
	
	//tables
	//value is MatchFile or TreeMap<Str,MatchFile>
	private Hashtable<Long,Object> files;

	//a flag that, when set, causes searching to stop
	private boolean stopFlag;
	
	//members that are used by the recursive match method
	private long n, length;

	/** Create a new MatchFinder. */
	public MatchFinder(MatchListener ml, ProgressListener pl, StatusListener sl){
		this.pl = pl;
		this.ml = ml;
		this.sl = sl;
		n = length = 0;
		files = new Hashtable<Long,Object>();
	}

	/**
		Start searching for matches in folder using ignore list.
	*/
	public void start(final String folder, final FilenameFilter ignore) 
		throws IOException, NoSuchAlgorithmException, FileNotFoundException{
		stopFlag=false;

		//check to make sure the folder exists
		if( !(new File(folder)).isDirectory() ){
			throw new FileNotFoundException(folder+" is not a folder.");
		}
		
		//create a new table
		n = length = 0;
		files.clear();

		//start a background process for counting the total number of files we
		//will be scanning
		Runnable r = new Runnable(){
			public void run(){
				try{ size(new File(folder), ignore); }
				catch(IOException iex){}
			}
		};
		Thread t = new Thread(r);
		t.start();

		//reset status variables
		n = length = 0;
		match(new MatchFolder(new File(folder), null), ignore);
		
		//free up tables
		files.clear();
		
		//notify listeners
		pl.setTotal(length);
		if(sl != null) sl.message("Finished.");
	}

	/** Stop the matching process. */
	public void stop(){
		stopFlag = true;
	}

	//match algorithm applied to a folder
	public void match(MatchFolder mf, FilenameFilter ignore) 
		throws IOException,NoSuchAlgorithmException{

		//extract the file reference from the MatchFolder and list it's children
		File fi = mf.getFile();
		File[] list = fi.listFiles(ignore);
		
		//if it has no children (either we dont have list permissions on the
		//directory, or it isn't a directory) then just return
		if(list == null) return ;
		
		//store the matchfiles we create to wrap the directory contents in a 
		//temporary location so we can later update their display
		Match[] fim = new Match[list.length];
		int fimSize = 0;
		boolean folderMatch = false;
		
		//determine if each file is a match
		for (int i = 0; i < list.length; i++){
			//ignore sym links and files that can't be read
			if( isSymlink(list[i]) || !list[i].canRead()){}
			//apply match algorithm to each file
			else if(list[i].isFile()){
				//create a new matchfile reference
				MatchFile newMF = new MatchFile(list[i], mf);
				match(newMF);
				fim[fimSize++] = newMF;

				//update progress tracker
				length += list[i].length();
				n++;
				pl.setProgress(length);
			}
			//recursively process subdirectories
			else{
				MatchFolder newMF = new MatchFolder(list[i], mf);
				match(newMF, ignore);
				fim[fimSize++] = newMF;
			}
			//stop if we want to
			if(stopFlag) return ;
		}

		//apply match algorithm to see if this folder is a perfect match with
		//some other folder
		//System.out.println("----- Matching "+mf.getFile().getAbsolutePath()+" ---- ");
		
		//for each file in this folder
		MatchFolder[] candidateMatches = null;
		int candidateMatchesSize=0;
		for (int i = 0; i < fimSize; i++){

			//System.out.println("["+i+"] Candidates after File: "+fim[i].getFile().getName());


			//for the first file, its matches are the candidates
			if(i == 0){
				candidateMatchesSize = fim[0].getMatchCount();
				candidateMatches = new MatchFolder[fim[0].getMatchCount()];
				int c=0;
				for (int j = 0; j < candidateMatchesSize; j++){
					MatchFolder par = fim[0].getMatch(j).getParent();
					//if this folder is a candidate match for itself, skip it
					if(par.getFile().getAbsolutePath().equals(
						mf.getFile().getAbsolutePath())) continue;
					//add this as a candidate match
					candidateMatches[c++] = par;
				}
				candidateMatchesSize=c;
			}
			//for subsequent matches, perform an intersection operation on the
			//candidates of the current file and the previous candidates
			else{	
				//loop over all currently eligible candidates
				for (int j = 0; j < candidateMatchesSize; j++){
					MatchFolder f1 = candidateMatches[j];
					//make sure this file is a candidate of the ith file
					boolean found = false;
					for (int k = 0; k < fim[i].getMatchCount(); k++){
						MatchFolder f2 = fim[i].getMatch(k).getParent();
						//System.out.println("      "+f2.getFile().getAbsolutePath());
						if( f2.getFile().getAbsolutePath().equals(
							f1.getFile().getAbsolutePath()) ){
							found = true;
							break ;
						}
					}
					//if this candidate was not found, remove it from the list
					if(!found){
						//put last element from candidateMatches here, then dec size
						candidateMatches[j]=candidateMatches[candidateMatchesSize-1];
						candidateMatches[candidateMatchesSize-1] = null;
						candidateMatchesSize--;
					}
				}
			}

			//print out the current matches DEBUG
			for (int j = 0; j < candidateMatchesSize; j++){
				//System.out.println("   "+candidateMatches[j].getFile().getAbsolutePath());
			}

			//stop if we want to
			if(stopFlag) return ;

		}
	
		//we now know that the candidateMatches all contain all the files of our
		//folder. That means our folder is a subset of each candidateMatch. It
		//is possible that the candidateMatch contains more files than mf, but it
		//at LEAST contains all the files in mf
		for (int j = 0; j < candidateMatchesSize; j++){
			//if the candidateMatch is also a subset of our folder, they are equal
			if(!candidateMatches[j].isSubsetOf(mf,false)) continue ;

			//otherwise this is a legitimate match, so add it
			folderMatch = true;
			mf.addMatch(candidateMatches[j]);
			candidateMatches[j].addMatch(mf);
			
			//we do not have to add the matches of matches because they should
			//already be candidates

			//stop if we want to
			if(stopFlag) return ;
		}
	
		
		//if this folder is not a perfect match with some other folder, post
		//all of it's matches as individual matches
		if(!folderMatch){
			//keep track of what mappings have been reported in this folder
			//so the reverse mapping is not accidentally reported
			//(can happen for files in the same folder)
			//System.out.println("New Report Map");
			TreeMap<String,Integer> reported = new TreeMap<String,Integer>();
			
			//add all files found in this folder
			for (int i = 0; i < fimSize; i++){
				Match m2 = fim[i];
				//only add the first match from each match folder since it
				//defines an equivalence class of matches - if we add all the
				//matches, then we will be adding the class a number of times
				//equal to the number of items already in the class
				for (int j = 0; j < 1 && j < fim[i].getMatchCount(); j++){
					Match m1 = fim[i].getMatch(j);
					//figure out what the keys would be for this match (and the
					//reverse match) in the reported map
					String key = m1.getFile().getAbsolutePath()+"-"+
						m2.getFile().getAbsolutePath();
					String rkey = m2.getFile().getAbsolutePath()+"-"+
						m1.getFile().getAbsolutePath();
					if(!reported.containsKey(key) && !reported.containsKey(rkey)){
						//notify the listener and note that we reported this match
						//in the report map
						ml.addMatch(m1.getFile(), m2.getFile());
						reported.put(key,1);
						//System.out.println("PUT report ("+key+")");
					}
				}
			}

			//stop if we want to
			if(stopFlag) return ;
		}

	}

	//match algorithm applied to a file
	public void match(MatchFile mf) throws IOException, NoSuchAlgorithmException{
		Object o = files.get(mf.getLength());
		//there is not a file with this length in the table
		//just insert this as a Single MatchFile
		if( o == null ){
			//System.out.println("LEN PUT "+mf.getLength()+" -> "+mf.getFile().getAbsolutePath());				
			files.put(mf.getLength(), mf);
		}
		//if there is already at least 1 file with this length in the table
		//we have a collision
		else{
			TreeMap<String,MatchFile> map = null;
			//if it is a matchfile, this is the first collision
			//We need to make a TreeMap to hold the collisions
			if(o instanceof MatchFile){
				MatchFile old = (MatchFile)o;
				map = new TreeMap<String,MatchFile>();
				map.put(old.getHash(), old);
				files.put(mf.getLength(), map);
			}
			//otherwise it is a tree map
			else if(o instanceof TreeMap){
				map = (TreeMap<String,MatchFile>)o;
			}
			//internal error
			else{
				throw new MatchException("Unexpected object type in hash map.");
			}
			//query the tree map to see if there is a perfect match to this file
			MatchFile mf2 = map.get( mf.getHash() );
			//System.out.println(mf.getFile().getCanonicalPath()+" = "+mf.getHash());
			
			//no perfect match
			if(mf2 == null){
				//System.out.println("[LEN="+mf.getLength()+"] HASH PUT "+mf.getHash()+" -> "+mf.getFile().getAbsolutePath());				
				map.put(mf.getHash(), mf);
			}
			//we found a file match!!!
			else{
				//System.out.println("File match found for "+mf.getFile().getAbsolutePath());

				//System.out.println("   Main Match "+mf2.getFile().getAbsolutePath());
			
				//add link between mf and the matches of the match as well
				for(int i=0; i < mf2.getMatchCount(); i++){
					MatchFile mf2c = (MatchFile)mf2.getMatch(i);
					//System.out.println("   Match of Match "+mf2c.getFile().getAbsolutePath());
					mf2c.addMatch(mf);
					mf.addMatch(mf2c);
				}
				//add a link between mf and the match
				mf2.addMatch(mf);
				mf.addMatch(mf2);
			}
		}
		
	}


	/** Recursively compute the size of a directory. */
	public long size(File f, FilenameFilter ignore) throws IOException{
		long length=0;
		Stack<File> s = new Stack<File>();
		s.push(f);
		long n=0;
		if(sl != null) sl.message("Counting...");
		while(!s.empty()){
			File fi = s.pop();
			File[] list = fi.listFiles(ignore);
			if(list == null) continue ;
			for (int i = 0; i < list.length; i++){
				//if stop flag is set, return
				if(stopFlag) return -1;				
				//ignore sym links and files that can't be read
				if( isSymlink(list[i]) || !list[i].canRead()){}
				//count file sizes
				else if(list[i].isFile()){
					length += list[i].length();
					if(pl != null && n%10000 == 0) pl.setTotal(length);
					n++;
				}
				//push dirs onto the stack
				else s.push(list[i]);

				//stop if we want to
				if(stopFlag) return -1;
			}
		}
		pl.setTotal(length);
		if(sl != null) sl.message("Searching...");
		return length;
	}

	//determine if a file is a sym link
	//http://stackoverflow.com/questions/813710/java-1-6-determine-symbolic-links
	public static boolean isSymlink(File file) throws IOException {
		if (file == null) throw new NullPointerException("File must not be null");
		File canon;
		if (file.getParent() == null) {
			canon = file;
		}
		else {
			File canonDir = file.getParentFile().getCanonicalFile();
			canon = new File(canonDir, file.getName());
		}
		return !canon.getCanonicalFile().equals(canon.getAbsoluteFile());
	}

}
